#include <stdio.h>
#include "single_linked_list.cpp"

// 带头结点链表, 增序输出, 不可以使用辅助数组 并释放空间
void IncrPrint(LinkedList &L) {
    while (L->next != NULL)
    {
        LNode *ptr = L->next; // 遍历L的节点
        LNode *min = L; // 记录最小的节点的前驱
        while(ptr->next != NULL) {
            if (ptr->next->data < min->next->data)
                min = ptr;
            ptr = ptr->next;
        }
        printf("%d ", min->next->data);
        LNode *q = min->next;
        min->next = min->next->next;
        free(q);
    }
}

int main() {
    LinkedList L;
    InitList(L);

    // 插入
    ListAppend(L, 2);
    ListAppend(L, 5);
    ListAppend(L, 9);
    ListAppend(L, 7);
    ListAppend(L, 3);
    ListAppend(L, 6);
    PrintList(L);

    IncrPrint(L);
    return 0;
}